package listbyorder.access101_200.test164;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/13 13:40
 */
public class Solution1 {

    // 鸽巢原理，10个萝卜11个坑，肯定有两个距离很大的
    public int maximumGap(int[] nums) {
        if(nums == null || nums.length < 2) return 0;

        int len = nums.length;
        // 首先遍历数组，找到数组中的最大值和最小值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++){
            min = Math.min(min,nums[i]);
            max = Math.max(max,nums[i]);
        }
        if(min == max) return 0;

        // 创建辅助数组
        int[] mins = new int[len + 1];
        int[] maxs = new int[len + 1];
        boolean[] exists = new boolean[len + 1];
        int index = 0;
        for(int i = 0; i < len; i++){
            index = getBucket(nums[i],len,min,max);
            if(exists[index]){
                mins[index] = Math.min(mins[index],nums[i]);
                maxs[index] = Math.max(maxs[index],nums[i]);
            }else{
                exists[index] = true;
                mins[index] = nums[i];
                maxs[index] = nums[i];
            }
        }
        int res = 0;
        int lastMax = maxs[0];

        for(int i = 1; i <= len; i++){
            if(exists[i]){
                res = Math.max(res,mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    private int getBucket(long num, long len, long min, long max) {
        return (int)((num - min) * len / (max - min));
    }
}
